{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Strength of a Group"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #backtracking #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #回溯 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxStrength"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #一个小组的最大实力值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;，它表示一个班级中所有学生在一次考试中的成绩。老师想选出一部分同学组成一个 <strong>非空</strong>&nbsp;小组，且这个小组的 <strong>实力值</strong>&nbsp;最大，如果这个小组里的学生下标为&nbsp;<code>i<sub>0</sub></code>, <code>i<sub>1</sub></code>, <code>i<sub>2</sub></code>, ... , <code>i<sub>k</sub></code>&nbsp;，那么这个小组的实力值定义为&nbsp;<code>nums[i<sub>0</sub>] * nums[i<sub>1</sub>] * nums[i<sub>2</sub>] * ... * nums[i<sub>k</sub>​]</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回老师创建的小组能得到的最大实力值为多少。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [3,-1,-5,2,5,-9]\n",
    "<strong>输出：</strong>1350\n",
    "<b>解释：</b>一种构成最大实力值小组的方案是选择下标为 [0,2,3,4,5] 的学生。实力值为 3 * (-5) * 2 * 5 * (-9) = 1350 ，这是可以得到的最大实力值。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [-4,-5,-4]\n",
    "<b>输出：</b>20\n",
    "<b>解释：</b>选择下标为 [0, 1] 的学生。得到的实力值为 20 。我们没法得到更大的实力值。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 13</code></li>\n",
    "\t<li><code>-9 &lt;= nums[i] &lt;= 9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-strength-of-a-group](https://leetcode.cn/problems/maximum-strength-of-a-group/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-strength-of-a-group](https://leetcode.cn/problems/maximum-strength-of-a-group/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,-1,-5,2,5,-9]', '[-4,-5,-4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        res = float('-inf')\n",
    "\n",
    "        for i in range(1, 1 << len(nums)):\n",
    "            val = 1\n",
    "\n",
    "            for j in range(len(nums)):\n",
    "                if i & (1 << j):\n",
    "                    val *= nums[j]\n",
    "            \n",
    "            res = max(res, val)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        if (nums.count(0) == len(nums)):\n",
    "            return 0\n",
    "        \n",
    "\n",
    "        ans = 1\n",
    "        for i in nums:\n",
    "            if (i!=0):\n",
    "                ans= i*ans\n",
    "        if(ans>0 or len(nums) == 1):\n",
    "            return ans\n",
    "        if (nums.count(0) == len(nums) - 1 and ans<0):\n",
    "            return 0\n",
    "        for i in range(1,10,1):\n",
    "            if (-i in nums):\n",
    "                return int(ans/(-i))\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        res = float('-inf')\n",
    "\n",
    "        for i in range(1, 1 << len(nums)):\n",
    "            val = 1\n",
    "\n",
    "            for j in range(len(nums)):\n",
    "                if i & (1 << j):\n",
    "                    val *= nums[j]\n",
    "            \n",
    "            res = max(res, val)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        ans = 1\n",
    "        n = len(nums)\n",
    "        max_neg = maxx = float('-inf')\n",
    "        selected_num = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] != 0:\n",
    "                ans *= nums[i]\n",
    "                selected_num += 1\n",
    "            if nums[i] < 0:\n",
    "                max_neg = max(max_neg, nums[i])\n",
    "            maxx = max(maxx, nums[i])\n",
    "        if selected_num <= 1:\n",
    "            return maxx\n",
    "        return ans // max_neg if ans < 0 else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums) -> int:\n",
    "        n = len(nums)\n",
    "        if n==1:\n",
    "            return nums[0]\n",
    "        nums = sorted(nums, key=lambda x: abs(x), reverse=True)\n",
    "        neg = 0\n",
    "        for num in nums:\n",
    "            if num <= -1:\n",
    "                neg += 1\n",
    "        if max(nums) == 0:\n",
    "            if neg <= 1:\n",
    "                return 0\n",
    "        res, ct = 1, 0\n",
    "        ct_max = (neg // 2) * 2\n",
    "        for num in nums:\n",
    "            if num > 1:\n",
    "                res *= num\n",
    "            elif num <= -1 and ct < ct_max:\n",
    "                res *= num\n",
    "                ct += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        neg,zero,pos = 0,0,0\n",
    "        ans = 1\n",
    "        length = len(nums)\n",
    "        for n in nums:\n",
    "            if n<0:\n",
    "                neg += 1\n",
    "            elif n==0:\n",
    "                zero += 1\n",
    "            else:\n",
    "                pos += 1\n",
    "        nums.sort()\n",
    "        if neg>0 and neg%2 == 1:\n",
    "            neg -= 1\n",
    "        for i in range(neg):\n",
    "            ans*=nums[i]\n",
    "        if pos>0:\n",
    "            for i in range(length-pos,length):\n",
    "                ans*=nums[i]\n",
    "        if pos==0 and ans==1:\n",
    "            if length==1:\n",
    "                return nums[0]\n",
    "            if neg>1:\n",
    "                return ans\n",
    "            return 0\n",
    "        return ans \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxStrength(self, nums):\n",
    "        if len(nums) == 1: return nums[0]        \n",
    "        lstneg = [n for n in nums if n < 0]\n",
    "        if len(lstneg) & 1: \n",
    "            nums.remove(max(lstneg))\n",
    "        nums = [n for n in nums if n]\n",
    "        return reduce(lambda x, y : x * y, nums) if nums else 0        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        po_s = [i for i in nums if i > 0]\n",
    "        ne_s = [i for i in nums if i < 0]\n",
    "        has_zero = bool([i for i in nums if i == 0])\n",
    "        if not po_s and len(ne_s) <= 1:\n",
    "            if has_zero:\n",
    "                return 0\n",
    "            if len(ne_s) == 1:\n",
    "                return ne_s[0]\n",
    "        res = 1\n",
    "        for i in po_s:\n",
    "            res *= i\n",
    "        ne_s.sort()\n",
    "        while len(ne_s) > 1:\n",
    "            a = ne_s[0]\n",
    "            b = ne_s[1]\n",
    "            ne_s = ne_s[2:]\n",
    "            tmp = a * b\n",
    "            res *= tmp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maxStrength(self, nums: List[int]) -> int:\n",
    "#         length = len(nums)\n",
    "#         nums = sorted(nums, key = lambda x: -x)\n",
    "#         ans = 1\n",
    "#         if length == 1:\n",
    "#             return nums[0]\n",
    "#         elif nums[-2] == 0 and nums[0] == 0:\n",
    "#             return 0\n",
    "#         ptr = 0\n",
    "#         while ptr < length:\n",
    "#             i = nums[ptr]\n",
    "#             if i > 0:\n",
    "#                 ans *= i\n",
    "#                 ptr += 1\n",
    "#             else:\n",
    "#                 break\n",
    "#         pr = length - 1\n",
    "#         while pr > ptr:\n",
    "#             if pr - 1 >= 0 and nums[pr] < 0 and nums[pr - 1] < 0:\n",
    "#                 ans *= nums[pr] * nums[pr - 1]\n",
    "#                 pr -= 2\n",
    "#             else:\n",
    "#                 break\n",
    "#         return max(ans, nums[0])\n",
    "        \n",
    "\n",
    "class Solution (object):\n",
    "    def maxStrength (self, nums):\n",
    "        if len (nums) == 1: return nums [0]        \n",
    "        lstneg = [n for n in nums if n < 0]\n",
    "        if len (lstneg) & 1: \n",
    "            nums.remove (max (lstneg))\n",
    "        nums = [n for n in nums if n]\n",
    "        return reduce (lambda x, y : x * y, nums) if nums else 0        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        ans = -inf\n",
    "        for i in range(1, len(nums)+1):\n",
    "            combines = itertools.combinations(nums, i)\n",
    "            for combine in combines:\n",
    "                ans = max(ans, math.prod(combine))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        # ans = -inf\n",
    "        # def dfs(i:int, prod:int, is_empty:bool) -> None:\n",
    "        #     if i == len(nums):\n",
    "        #         if not is_empty:\n",
    "        #             nonlocal ans\n",
    "        #             ans = max(ans,prod)\n",
    "        #         return \n",
    "        #     dfs(i+1,prod,is_empty)\n",
    "        #     dfs(i+1,prod*nums[i],False)\n",
    "        # dfs(0,1,True)\n",
    "        # return ans\n",
    "        mx = mn = nums[0]\n",
    "        for x in nums[1:]:\n",
    "            tmp = mx\n",
    "            mx = max(mx,x,x*mx,x*mn)\n",
    "            mn = min(mn,x,x*tmp,x*mn)\n",
    "        return mx\n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        else:\n",
    "            l = [0, 0]\n",
    "            for i in nums:\n",
    "                if i<0:\n",
    "                    l[0] += 1\n",
    "                elif i>0:\n",
    "                    l[1] += 1\n",
    "            if (l[0]==1 or l[0]==0) and l[1]==0:\n",
    "                return max(nums)\n",
    "\n",
    "            flag = min(nums)\n",
    "            res = 1\n",
    "            for i in nums:\n",
    "                if i!=0:\n",
    "                    res *= i\n",
    "                if flag<i<0:\n",
    "                    flag = i\n",
    "            return res if res>0 else res//flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        min_l = [nums[0]]\n",
    "        max_l = [nums[0]]\n",
    "        for i in range(1, len(nums)):\n",
    "            min_l.append(min(max_l[i-1] * nums[i], min_l[i-1] * nums[i], nums[i], min_l[i-1]))\n",
    "            max_l.append(max(max_l[i-1] * nums[i], min_l[i-1] * nums[i], nums[i], max_l[i-1]))\n",
    "        return max_l[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "        f = [num for num in nums if num<0]\n",
    "        if len(f)&1:\n",
    "            nums.remove(max(f))\n",
    "        nums = [n for n in nums if n]\n",
    "        return reduce(lambda a,b: a*b, nums) if nums else 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxStrength(self, nums):\n",
    "        if len(nums) == 1: return nums[0]        \n",
    "        lstneg = [n for n in nums if n < 0]\n",
    "        if len(lstneg) & 1: \n",
    "            nums.remove(max(lstneg))\n",
    "        nums = [n for n in nums if n]\n",
    "        return reduce(lambda x, y : x * y, nums) if nums else 0        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        res = None\n",
    "        neg = 0\n",
    "        zero = 0\n",
    "        max_neg = None\n",
    "        for v in nums:\n",
    "            if v == 0:\n",
    "                zero += 1\n",
    "            else:\n",
    "                if res is None:\n",
    "                    res = v\n",
    "                else:\n",
    "                    res *= v\n",
    "                if v < 0:\n",
    "                    neg += 1\n",
    "                    if max_neg is None or max_neg < v:\n",
    "                        max_neg = v\n",
    "\n",
    "        if res is None:\n",
    "            res = 0\n",
    "        elif res < 0 and len(nums) > 1:\n",
    "            if neg == 1 and neg + zero == len(nums):\n",
    "                res = 0\n",
    "            else:\n",
    "                res //= max_neg\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        else:\n",
    "            a, b = 0, 0\n",
    "            flag = min(nums)\n",
    "            res = 1\n",
    "            for i in nums:\n",
    "                if i<0:\n",
    "                    a += 1\n",
    "                    res *= i\n",
    "                    flag = max(flag, i)\n",
    "                elif i>0:\n",
    "                    b += 1\n",
    "                    res *= i\n",
    "            if a<2 and b==0:\n",
    "                return max(nums)\n",
    "            return res if res>0 else res//flag\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        else:\n",
    "            l = [0, 0]\n",
    "            for i in nums:\n",
    "                if i<0:\n",
    "                    l[0] += 1\n",
    "                elif i>0:\n",
    "                    l[1] += 1\n",
    "            if (l[0]==1 or l[0]==0) and l[1]==0:\n",
    "                return max(nums)\n",
    "\n",
    "            flag = min(nums)\n",
    "            res = 1\n",
    "            for i in nums:\n",
    "                if i!=0:\n",
    "                    res *= i\n",
    "                if flag<i<0:\n",
    "                    flag = i\n",
    "            return res if res>0 else res//flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "        nums = sorted(nums)\n",
    "        ans = 1\n",
    "        tag = 0\n",
    "        count1 = 0\n",
    "        for num in nums:\n",
    "            if num < 0:\n",
    "                count1 += 1\n",
    "            elif num > 0:\n",
    "                tag = 1\n",
    "                ans *= num\n",
    "        \n",
    "        if tag == 0 and count1 < 2:\n",
    "            return 0\n",
    "\n",
    "        pair,i,j =0, 0, 1\n",
    "        while pair < count1//2:\n",
    "            ans *= nums[i] * nums[j]\n",
    "            i += 2\n",
    "            j += 2\n",
    "            pair += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        xiao = 0\n",
    "        fei = 0\n",
    "        result = 1\n",
    "        for i in nums:\n",
    "            if i != 0:\n",
    "                result = result * i\n",
    "                fei = fei + 1\n",
    "            if i < 0 :\n",
    "                xiao = xiao + 1\n",
    "        if xiao == 1 and fei == 1:\n",
    "            return 0\n",
    "        if fei == 0:\n",
    "            return 0\n",
    "        fla = -999999\n",
    "        for i in nums:\n",
    "            if i > fla and i < 0 :\n",
    "                fla = i\n",
    "            if i > 0:\n",
    "                break\n",
    "        if result < 0 :\n",
    "            result = result / fla\n",
    "        return(int(result))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        \n",
    "        nums.sort()\n",
    "        i=0\n",
    "        flag=False\n",
    "        while i<len(nums):\n",
    "            if nums[i]==0:\n",
    "                flag=True\n",
    "                del nums[i]\n",
    "            else:\n",
    "                i+=1\n",
    "        if len(nums)==1:\n",
    "            if nums[0]<0 and flag:\n",
    "                return 0\n",
    "\n",
    "            return nums[0]\n",
    "        if not nums:\n",
    "            return 0\n",
    "        n=len(nums)\n",
    "        x=n\n",
    "        for i in range(n):\n",
    "            \n",
    "            if nums[i]>0:\n",
    "                x=i\n",
    "                break\n",
    "        a=1\n",
    "        b=1\n",
    "        for i in range(x):\n",
    "            a*=nums[i]\n",
    "        if x%2!=0:\n",
    "            a=a//nums[x-1]\n",
    "        for i in range(x,n):\n",
    "            b*=nums[i]\n",
    "        return a*b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        dpmin = nums[0]\n",
    "        dpmax = nums[0]\n",
    "\n",
    "        for i in range(1,len(nums)):\n",
    "            \n",
    "            tempmax = dpmax\n",
    "            dpmax = max(dpmax * nums[i],nums[i], dpmax , dpmin * nums[i])\n",
    "            print(dpmax)\n",
    "            dpmin = min(tempmax * nums[i],nums[i], dpmin , dpmin * nums[i])\n",
    "            print(dpmin)\n",
    "        return dpmax\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        neg = sorted(x for x in nums if x < 0)\n",
    "        pos = [x for x in nums if x > 0]\n",
    "        if len(pos) == 0 and len(neg) <= 1:\n",
    "            if len(neg) == 0:\n",
    "                return 0\n",
    "            return neg[0] if 0 not in nums else 0\n",
    "        ans = 1\n",
    "        for x in pos:\n",
    "            ans *= x\n",
    "        if len(neg) & 1:\n",
    "            for x in neg[:-1]:\n",
    "                ans *= x\n",
    "        else:\n",
    "            for x in neg:\n",
    "                ans *= x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        res = 1\n",
    "        m = 100\n",
    "        c = 0\n",
    "        cp = 0\n",
    "        z = 0\n",
    "        for i in nums:\n",
    "            if i != 0:\n",
    "                res *= i\n",
    "            if i < 0:\n",
    "                c += 1\n",
    "                if m > -i:\n",
    "                    m = -i\n",
    "            elif i > 0:\n",
    "                cp += 1\n",
    "        print(c,cp,m)\n",
    "        if cp > 0 or c > 1:\n",
    "            pass\n",
    "        \n",
    "        elif c == 1:\n",
    "            if c == len(nums):\n",
    "                return -m\n",
    "            else:\n",
    "                return 0\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "        if c // 2 * 2 != c:\n",
    "            print('--------------')\n",
    "            return - res // m\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        mx = mn = nums[0]\n",
    "\n",
    "        for x in nums[1:]:\n",
    "            tmp =mx\n",
    "            mx = max(mx,mx*x,mn*x,x)\n",
    "            mn = min(mn,tmp*x,mn*x,x)\n",
    "\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        # 二进制写法\n",
    "        n = len(nums)\n",
    "        maxPower = -float('inf')\n",
    "        for mask in range(1,1<<n):\n",
    "            curPower = 1\n",
    "            for i in range(n):\n",
    "                if mask & (1<<i):\n",
    "                    curPower *= nums[i]\n",
    "            maxPower = max(maxPower,curPower)\n",
    "        return maxPower"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        result = float(\"-inf\")\n",
    "        sub = list()\n",
    "\n",
    "        def calc(sub):\n",
    "            result = 1\n",
    "            for num in sub:\n",
    "                result *= num\n",
    "            return result\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal result\n",
    "            if i == n:\n",
    "                tmp = calc(sub)\n",
    "                if sub and tmp > result:\n",
    "                    result = tmp\n",
    "                return\n",
    "            dfs(i+1)\n",
    "            sub.append(nums[i])\n",
    "            dfs(i+1)\n",
    "            sub.pop()\n",
    "\n",
    "        dfs(0)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1: \n",
    "            return nums[0]\n",
    "        ans = 1\n",
    "        minneg = min(nums)\n",
    "        Num = 0\n",
    "        for i in nums:\n",
    "            if i != 0:\n",
    "                ans = ans * i\n",
    "                Num += 1\n",
    "            if i < 0:\n",
    "                if i > minneg:\n",
    "                    minneg = i\n",
    "        if Num == 0: return 0\n",
    "        if ans < 0:\n",
    "            ans = ans/minneg\n",
    "            if Num == 1: return 0\n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        neg = []\n",
    "        pos = []\n",
    "        for n in nums:\n",
    "            if n > 0:\n",
    "                pos.append(n)\n",
    "            elif n < 0:\n",
    "                neg.append(n)\n",
    "        if not pos and len(neg) <= 1:\n",
    "            return 0\n",
    "        neg.sort()\n",
    "        if len(neg) & 1:\n",
    "            neg.pop()\n",
    "        return prod(neg) * prod(pos)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        ls1=[]\n",
    "        ls2=[]\n",
    "        ls3=[]\n",
    "        for num in nums:\n",
    "            if num>0:\n",
    "                ls1.append(num)\n",
    "            elif num<0:\n",
    "                ls2.append(num)\n",
    "            else:\n",
    "                ls3.append(num)\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        elif ls1==[] and (0 in ls3) and len(ls2)<=1:\n",
    "            return 0\n",
    "        result=1\n",
    "        for num in ls1:\n",
    "            result=result*num\n",
    "        if len(ls2)%2==0:\n",
    "            for num in ls2:\n",
    "                result=result*num\n",
    "        else:\n",
    "            ls2.sort()\n",
    "            for i in range(len(ls2)-1):\n",
    "                result=result*ls2[i]\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        # 1.取绝对值后，排序\n",
    "        # 2.直接遍历，如果是正则直接乘，如果是负，放到新数组，排序后取前偶数个\n",
    "        # 选中子数组 有负号的数据cnt必须为偶数\n",
    "        res = 1\n",
    "        minors = []\n",
    "        zero = False\n",
    "        bigger0 = False \n",
    "        for num in nums:\n",
    "            if num > 0:\n",
    "                res *= num\n",
    "                bigger0 = True\n",
    "            elif num == 0:\n",
    "                zero = True\n",
    "            else:\n",
    "                minors.append(num)\n",
    "\n",
    "        n = len(minors) \n",
    "        if n > 1 and n % 2 == 0:\n",
    "            minors.sort()\n",
    "            for each in minors:\n",
    "                res *= each\n",
    "                print(each,res)\n",
    "        elif n > 1 and n % 2 != 0:\n",
    "            minors.sort()\n",
    "            for each in minors[:n-1]:\n",
    "                res *= each\n",
    "        elif bigger0 == False and zero == True:\n",
    "            res = 0\n",
    "        elif bigger0 == False and zero == False:\n",
    "            res = minors[-1]\n",
    "        \n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "        \n",
    "        pos, has_pos = 1, False\n",
    "        neg, max_neg, cnt = 1, -inf, 0\n",
    "        for x in nums:\n",
    "            if x > 0:\n",
    "                has_pos = True\n",
    "                pos *= x\n",
    "            elif x < 0:\n",
    "                neg *= x\n",
    "                max_neg = max(max_neg, x)\n",
    "                cnt += 1\n",
    "        \n",
    "        if has_pos:\n",
    "            return pos * (neg if neg > 0 else neg // max_neg)\n",
    "        \n",
    "        return 0 if cnt <= 1 else neg if neg > 0 else neg // max_neg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ret = nums[0]\n",
    "        for i in range(1, 1 << n):\n",
    "            s = 1\n",
    "            for j in range(n):\n",
    "                if i & 1 << j:\n",
    "                    s *= nums[j]\n",
    "            ret = max(ret, s)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        curMax, curMin = nums[0], nums[0]\n",
    "        for num in nums[1 : ]:\n",
    "            curMax, curMin = max(num, curMax * num, curMin * num, curMax), min(num, curMax * num, curMin * num, curMin)\n",
    "        return curMax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        if len(nums)== 1:\n",
    "            return nums[0]\n",
    "        ans=1\n",
    "        have_0=0\n",
    "        cnt1=0\n",
    "        cnt2=0\n",
    "        for n in nums:\n",
    "            if n:\n",
    "                ans*=n\n",
    "                if n>0:\n",
    "                    cnt1+=1\n",
    "                if n<0:\n",
    "                    cnt2+=1\n",
    "            else:\n",
    "                have_0=1\n",
    "        if have_0 and cnt1==0 and cnt2<=1:\n",
    "            return 0\n",
    "        \n",
    "        if ans<0:\n",
    "            min_val=-inf\n",
    "            for n in nums:\n",
    "                if n<0 and n>min_val:\n",
    "                    min_val=n\n",
    "            ans//=min_val\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        pos = [i for i in nums if i > 0]\n",
    "        neg = [i for i in nums if i < 0]\n",
    "        neg.sort()\n",
    "\n",
    "        zero = False\n",
    "        if 0 in nums:\n",
    "            zero = True\n",
    "\n",
    "        if not pos and len(neg) <= 1:\n",
    "            if zero:\n",
    "                return 0\n",
    "            return neg[0]\n",
    "\n",
    "        n = len(neg)\n",
    "        if n % 2 != 0:\n",
    "            neg.pop()\n",
    "\n",
    "        ans = 1\n",
    "        for x in pos+neg:\n",
    "            ans *= x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "        nums = sorted(nums)\n",
    "        ans = 1\n",
    "        tag = 0\n",
    "        count1 = 0\n",
    "        for num in nums:\n",
    "            if num < 0:\n",
    "                count1 += 1\n",
    "            elif num > 0:\n",
    "                tag = 1\n",
    "                ans *= num\n",
    "        \n",
    "        if tag == 0 and count1 < 2:\n",
    "            return 0\n",
    "\n",
    "        pair,i,j =0, 0, 1\n",
    "        while pair < count1//2:\n",
    "            ans *= nums[i] * nums[j]\n",
    "            i += 2\n",
    "            j += 2\n",
    "            pair += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        dp = [[0] * 2 for _ in range(len(nums))]\n",
    "        # dp[i][0]:最大, [i][1]:最小\n",
    "        dp[0][0] = dp[0][1] = nums[0]\n",
    "\n",
    "        res = dp[0][0]\n",
    "\n",
    "        for i in range(1, len(dp)):\n",
    "            dp[i][0] = dp[i][1] = nums[i]\n",
    "\n",
    "            dp[i][0] = max(dp[i][0], dp[i - 1][0], dp[i - 1][0] * nums[i], dp[i - 1][1] * nums[i])\n",
    "            dp[i][1] = min(dp[i][1], dp[i - 1][1], dp[i - 1][0] * nums[i], dp[i - 1][1] * nums[i])\n",
    "            \n",
    "            \n",
    "        return dp[-1][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        sum=1\n",
    "        nums.sort()\n",
    "\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        ne=[]\n",
    "        for i in nums:\n",
    "            if i >0:\n",
    "                sum*=i\n",
    "            elif i<0:\n",
    "                sum*=i\n",
    "                ne+=[i]\n",
    "        if nums[-1]==0:\n",
    "            if nums[1]==0:\n",
    "                return 0\n",
    "        if len(ne)%2!=0:\n",
    "            sum//=ne[-1]\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n==1:\n",
    "            return nums[0]\n",
    "        positive = [float('-inf')] * n\n",
    "        negative = [float('inf')] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            if i == 0:\n",
    "                if x > 0:\n",
    "                    positive[i] = x\n",
    "                if x < 0:\n",
    "                    negative[i] = x\n",
    "                continue\n",
    "            if x > 0:\n",
    "                premaxpositive = max(positive)\n",
    "                preminnegative = min(negative)\n",
    "                if premaxpositive == float('-inf'):\n",
    "                    positive[i] = x\n",
    "                else:\n",
    "                    positive[i] = x * premaxpositive\n",
    "                if preminnegative == float('inf'):\n",
    "                    negative[i] = float('inf')\n",
    "                else:\n",
    "                    negative[i] = preminnegative * x\n",
    "            if x < 0:\n",
    "                premaxpositive = max(positive)  # 获取整数组的最大值\n",
    "                preminnegative = min(negative)\n",
    "                if premaxpositive == float('-inf'):\n",
    "                    negative[i] = x\n",
    "                else:\n",
    "                    negative[i] = x * premaxpositive\n",
    "                if preminnegative == float('inf'):\n",
    "                    positive[i] = float('-inf')\n",
    "                else:\n",
    "                    positive[i] = x * preminnegative\n",
    "        a=max(positive)\n",
    "        return a if a!=-inf else 0 \n",
    "\n",
    "\n",
    "                \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        ans = -inf\n",
    "        def dfs(i:int, prod:int, is_empty:bool) -> None:\n",
    "            if i == len(nums):\n",
    "                if not is_empty:\n",
    "                    nonlocal ans\n",
    "                    ans = max(ans,prod)\n",
    "                return \n",
    "            dfs(i+1,prod,is_empty)\n",
    "            dfs(i+1,prod*nums[i],False)\n",
    "        dfs(0,1,True)\n",
    "        return ans\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        else:\n",
    "            a, b = 0, 0\n",
    "            flag = min(nums)\n",
    "            res = 1\n",
    "            for i in nums:\n",
    "                if i<0:\n",
    "                    a += 1\n",
    "                    res *= i\n",
    "                    flag = max(flag, i)\n",
    "                elif i>0:\n",
    "                    b += 1\n",
    "                    res *= i\n",
    "            if a<2 and b==0:\n",
    "                return max(nums)\n",
    "            return res if res>0 else res//flag\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        else:\n",
    "            l = [0, 0]\n",
    "            for i in nums:\n",
    "                if i<0:\n",
    "                    l[0] += 1\n",
    "                elif i>0:\n",
    "                    l[1] += 1\n",
    "            if (l[0]==1 or l[0]==0) and l[1]==0:\n",
    "                return max(nums)\n",
    "\n",
    "            flag = min(nums)\n",
    "            res = 1\n",
    "            for i in nums:\n",
    "                if i!=0:\n",
    "                    res *= i\n",
    "                if flag<i<0:\n",
    "                    flag = i\n",
    "            return res if res>0 else res//flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        nums = sorted(nums, key = lambda x: -x)\n",
    "        ans = 1\n",
    "        if length == 1:\n",
    "            return nums[0]\n",
    "        elif nums[-2] == 0 and nums[0] == 0:\n",
    "            return 0\n",
    "        ptr = 0\n",
    "        while ptr < length:\n",
    "            i = nums[ptr]\n",
    "            if i > 0:\n",
    "                ans *= i\n",
    "                ptr += 1\n",
    "            else:\n",
    "                break\n",
    "        pr = length - 1\n",
    "        while pr > ptr:\n",
    "            if pr - 1 >= 0 and nums[pr] < 0 and nums[pr - 1] < 0:\n",
    "                ans *= nums[pr] * nums[pr - 1]\n",
    "                pr -= 2\n",
    "            else:\n",
    "                break\n",
    "        return max(ans, nums[0])\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        \n",
    "        mx = mn = nums[0]\n",
    "        for x in nums[1:]:\n",
    "            tmp = mx\n",
    "            mx = max(mx, mx * x, mn * x, x)\n",
    "            mn = min(mn, tmp * x, mn * x, x)\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        nums.sort()\n",
    "        pos=bisect.bisect_left(nums,0)\n",
    "        res=0\n",
    "        for j in range(pos,len(nums)):\n",
    "            if not res:\n",
    "                res=nums[j]\n",
    "            else:\n",
    "                res*=nums[j]\n",
    "        for i in range(pos-1 if pos%2 else pos):\n",
    "            if not res:\n",
    "                res=nums[i]\n",
    "            else:\n",
    "                res*=nums[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        maxnegative = -10\n",
    "        negativecnt = 0\n",
    "        positive = 1\n",
    "        positivecnt = 0\n",
    "        negative = 1\n",
    "        zero = 0\n",
    "        for num in nums:\n",
    "            if num > 0:\n",
    "                positive *= num\n",
    "                positivecnt += 1\n",
    "            elif num < 0:\n",
    "                maxnegative = max(maxnegative, num)\n",
    "                negative *= num\n",
    "                negativecnt += 1\n",
    "            else:\n",
    "                zero += 1\n",
    "        if zero >= 1 and positivecnt == 0 and negativecnt <= 1:\n",
    "            return 0\n",
    "        if negativecnt == 1 and zero == 0 and positivecnt == 0:\n",
    "            return nums[0]\n",
    "        if negativecnt % 2:\n",
    "            negative = negative//maxnegative\n",
    "        return negative * positive\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        else:\n",
    "            l = [0, 0]\n",
    "\n",
    "            flag = min(nums)\n",
    "            res = 1\n",
    "            for i in nums:\n",
    "                if i<0:\n",
    "                    l[0] += 1\n",
    "                elif i>0:\n",
    "                    l[1] += 1\n",
    "                if i!=0:\n",
    "                    res *= i\n",
    "                if flag<i<0:\n",
    "                    flag = i\n",
    "            if (l[0]==1 or l[0]==0) and l[1]==0:\n",
    "                return max(nums)\n",
    "            return res if res>0 else res//flag\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        else:\n",
    "            l = [0, 0]\n",
    "            for i in nums:\n",
    "                if i<0:\n",
    "                    l[0] += 1\n",
    "                elif i>0:\n",
    "                    l[1] += 1\n",
    "            if (l[0]==1 or l[0]==0) and l[1]==0:\n",
    "                return max(nums)\n",
    "\n",
    "            flag = min(nums)\n",
    "            res = 1\n",
    "            for i in nums:\n",
    "                if i!=0:\n",
    "                    res *= i\n",
    "                if flag<i<0:\n",
    "                    flag = i\n",
    "            return res if res>0 else res//flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        df = list(sorted([-x for x in nums if x < 0],key=lambda x:-x))\n",
    "        sf = [x for x in nums if x > 0]\n",
    "        if len(sf) == 0 and len(df) == 1:\n",
    "            if 0 not in nums:\n",
    "                return -df[0]\n",
    "            else:\n",
    "                return 0\n",
    "        if len(sf) == 0 and len(df) == 0:\n",
    "            return 0\n",
    "        res = 1\n",
    "        for x in sf:\n",
    "            res *= x\n",
    "        for x in df:\n",
    "            res *= x\n",
    "        if len(df)%2 == 1:\n",
    "            res //= df[-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        # ans = -9\n",
    "        # n = len(nums)\n",
    "        # for i in range(1, 1 << n):\n",
    "        #     cur = 1\n",
    "        #     for j in range(n):\n",
    "        #         if i >> j & 1:\n",
    "        #             cur *= nums[j]\n",
    "        #     ans = max(ans, cur)\n",
    "        # return ans\n",
    "\n",
    "        mx = mn = nums[0]\n",
    "        for i in range(1, len(nums)):\n",
    "            x = nums[i]\n",
    "            mx, mn = max(mx, mx * x, mn * x, x), min(mn, mx * x, mn * x, x)\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        neg = []\n",
    "        pos = []\n",
    "        for n in nums:\n",
    "            if n > 0:\n",
    "                pos.append(n)\n",
    "            elif n < 0:\n",
    "                neg.append(n)\n",
    "        if not pos and len(neg) <= 1:\n",
    "            return 0\n",
    "        neg.sort()\n",
    "        if len(neg) & 1:\n",
    "            neg.pop()\n",
    "        return prod(neg) * prod(pos)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        # 回溯写法\n",
    "        def dfs(pos,num,res):\n",
    "            nonlocal ans\n",
    "            if pos == n:\n",
    "                if res != 0:\n",
    "                    ans = max(ans,num)\n",
    "                return\n",
    "            dfs(pos + 1,num * nums[pos],res + 1)\n",
    "            dfs(pos + 1,num,res)\n",
    "\n",
    "        n = len(nums)\n",
    "        ans = -float('inf')\n",
    "        dfs(0,1,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        a,b = [],[]\n",
    "        c = 0\n",
    "        for i in nums:\n",
    "            if i>0:\n",
    "                a.append(i)\n",
    "            elif i<0:\n",
    "                b.append(i)\n",
    "            else:\n",
    "                c += 1\n",
    "        \n",
    "        b.sort()\n",
    "\n",
    "        if len(a)>0 or len(b) >= 2:\n",
    "            if len(b)%2==1:\n",
    "                b.pop()\n",
    "            ret = 1\n",
    "            for i in a:\n",
    "                ret *= i\n",
    "            for i in b:\n",
    "                ret *= i\n",
    "            return ret\n",
    "        elif c>0:\n",
    "            return 0\n",
    "        else:\n",
    "            return b[-1]\n",
    "           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        res=-1<<31\n",
    "        n=len(nums)\n",
    "        for i in range(1,1<<n):\n",
    "            cur=1\n",
    "            for j in range(n):\n",
    "                if (1<<j)&i!=0:\n",
    "                    cur*=nums[j]\n",
    "            res=max(res,cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        self.ans=-inf\n",
    "        self.n=len(nums)\n",
    "        def dfs(i,nn,s):\n",
    "            if i==self.n:\n",
    "                if s!=0:\n",
    "                    self.ans=max(self.ans,nn)\n",
    "                return \n",
    "            dfs(i+1,nn*nums[i],s+1)\n",
    "            dfs(i+1,nn,s)\n",
    "        dfs(0,1,0)\n",
    "        return self.ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        else:\n",
    "            l = [0,0,0]\n",
    "            for i in nums:\n",
    "                if i<0:\n",
    "                    l[0] += 1\n",
    "                elif i>0:\n",
    "                    l[2] += 1\n",
    "                else:\n",
    "                    l[1] += 1\n",
    "            if (l[0]==1 or l[0]==0) and l[2]==0:\n",
    "                return max(nums)\n",
    "\n",
    "            flag = min(nums)\n",
    "            res = 1\n",
    "            for i in nums:\n",
    "                if i!=0:\n",
    "                    res *= i\n",
    "                if flag<i<0:\n",
    "                    flag = i\n",
    "            return res if res>0 else res//flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums) -> int:\n",
    "        n = len(nums)\n",
    "        if n==1:\n",
    "            return nums[0]\n",
    "        nums = sorted(nums, key=lambda x: abs(x), reverse=True)\n",
    "        neg = 0\n",
    "        for num in nums:\n",
    "            if num <= -1:\n",
    "                neg += 1\n",
    "        if max(nums) == 0:\n",
    "            if neg <= 1:\n",
    "                return 0\n",
    "        res, ct = 1, 0\n",
    "        ct_max = (neg // 2) * 2\n",
    "        for num in nums:\n",
    "            if num > 1:\n",
    "                res *= num\n",
    "            elif num <= -1 and ct < ct_max:\n",
    "                res *= num\n",
    "                ct += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1: return nums[0]\n",
    "        nums.sort()\n",
    "        numslow = [n for n in nums if n < 0]\n",
    "        numshigh = [n for n in nums if n > 0]\n",
    "        # print(numslow)\n",
    "        # print(numshigh)\n",
    "        res = 1\n",
    "        for i in numshigh:\n",
    "            res *= i\n",
    "        l = len(numslow)\n",
    "        if l % 2 == 1:\n",
    "            numslow = numslow[0:-1]\n",
    "        # print(numslow)\n",
    "        for i in numslow:\n",
    "            res *= i\n",
    "        return 0 if len(numshigh) == 0 and len(numslow) == 0 else res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        ans = -inf\n",
    "        for i in range(1, 1<<n):\n",
    "            lst = [nums[j] for j in range(n) if i  & (1<<j)]\n",
    "            cur = reduce(mul, lst)\n",
    "            if cur > ans:\n",
    "                ans = cur\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        else:\n",
    "            a, b = 0, 0\n",
    "            flag = min(nums)\n",
    "            res = 1\n",
    "            for i in nums:\n",
    "                if i<0:\n",
    "                    a += 1\n",
    "                    res *= i\n",
    "                    if flag<i:\n",
    "                        flag = i\n",
    "                elif i>0:\n",
    "                    b += 1\n",
    "                    res *= i\n",
    "            if a<2 and b==0:\n",
    "                return max(nums)\n",
    "            return res if res>0 else res//flag\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        else:\n",
    "            l = [0, 0]\n",
    "            for i in nums:\n",
    "                if i<0:\n",
    "                    l[0] += 1\n",
    "                elif i>0:\n",
    "                    l[1] += 1\n",
    "            if (l[0]==1 or l[0]==0) and l[1]==0:\n",
    "                return max(nums)\n",
    "\n",
    "            flag = min(nums)\n",
    "            res = 1\n",
    "            for i in nums:\n",
    "                if i!=0:\n",
    "                    res *= i\n",
    "                if flag<i<0:\n",
    "                    flag = i\n",
    "            return res if res>0 else res//flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        neg_group = []\n",
    "        res = 1\n",
    "        group_cnt = 0\n",
    "        zero_flag = 0\n",
    "        for i in nums:\n",
    "            if i > 0:\n",
    "                res *= i\n",
    "                group_cnt += 1\n",
    "            elif i < 0:\n",
    "                neg_group.append(i)\n",
    "            else:\n",
    "                zero_flag = 1\n",
    "                continue\n",
    "        neg_group.sort()\n",
    "        if len(neg_group) %2 == 0:\n",
    "            for i in neg_group:\n",
    "                group_cnt += 1\n",
    "                res *= i\n",
    "        else:\n",
    "            for i in neg_group[:-1]:\n",
    "                group_cnt += 1\n",
    "                res *= i\n",
    "        if group_cnt == 0:\n",
    "            if  zero_flag ==1:\n",
    "                return  0\n",
    "            else:\n",
    "                return nums[0]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        prod = 1\n",
    "        nums_below_zero = []\n",
    "        for num in nums:\n",
    "            if num > 0:\n",
    "                prod *= num\n",
    "            elif num < 0:\n",
    "                nums_below_zero.append(num)\n",
    "        # nums_below_zero.sort(reverse=True)\n",
    "        prod2 = math.prod(nums_below_zero)\n",
    "        n = len(nums_below_zero)\n",
    "        if n & 1:\n",
    "            min_ = max(nums_below_zero)\n",
    "        else:\n",
    "            min_ = 1\n",
    "        #while i >= 2:\n",
    "        \n",
    "        \n",
    "        #    i -= 2\n",
    "        if n < 2 and prod == 1:\n",
    "            if 1 in nums:\n",
    "                return 1\n",
    "            elif 0 in nums:\n",
    "                return 0\n",
    "            else:\n",
    "                return nums_below_zero[0]\n",
    "\n",
    "        prod = prod * prod2 // min_\n",
    "        return prod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        prod = 1\n",
    "        nums_below_zero = []\n",
    "        for num in nums:\n",
    "            if num > 0:\n",
    "                prod *= num\n",
    "            elif num < 0:\n",
    "                nums_below_zero.append(num)\n",
    "\n",
    "        prod2 = math.prod(nums_below_zero)\n",
    "        n = len(nums_below_zero)\n",
    "        if n & 1:\n",
    "            min_ = max(nums_below_zero)\n",
    "        else:\n",
    "            min_ = 1\n",
    "\n",
    "        if n < 2 and prod == 1:\n",
    "            if 1 in nums:\n",
    "                return 1\n",
    "            elif 0 in nums:\n",
    "                return 0\n",
    "            else:\n",
    "                return nums_below_zero[0]\n",
    "\n",
    "        prod = prod * prod2 // min_\n",
    "        return prod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        nums = sorted(nums, key = lambda x: -x)\n",
    "        ans = 1\n",
    "        if length == 1:\n",
    "            return nums[0]\n",
    "        elif nums[-2] == 0 and nums[0] == 0:\n",
    "            return 0\n",
    "        ptr = 0\n",
    "        while ptr < length:\n",
    "            i = nums[ptr]\n",
    "            if i > 0:\n",
    "                ans *= i\n",
    "                ptr += 1\n",
    "            else:\n",
    "                break\n",
    "        pr = length - 1\n",
    "        while pr > ptr:\n",
    "            if pr - 1 >= 0 and nums[pr] < 0 and nums[pr - 1] < 0:\n",
    "                ans *= nums[pr] * nums[pr - 1]\n",
    "                pr -= 2\n",
    "            else:\n",
    "                break\n",
    "        return ans\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        nums.sort() \n",
    "        n = len(nums)\n",
    "        idx = bisect_left(nums, 1) \n",
    "        if idx == n:\n",
    "            idx2 = bisect_left(nums,0)\n",
    "            if idx2 % 2 == 1:\n",
    "                if idx2 == 1:\n",
    "                    if idx2 == n:\n",
    "                        return nums[0]\n",
    "                    else:\n",
    "                        return 0 \n",
    "                else:\n",
    "                    tot = 1 \n",
    "                    for i in range(idx2-1):\n",
    "                        tot *= nums[i]\n",
    "                    return tot \n",
    "            else:\n",
    "                if idx2 == 0:\n",
    "                    return 0\n",
    "                tot = 1\n",
    "                for i in range(idx2):\n",
    "                    tot *= nums[i] \n",
    "                return tot \n",
    "        else:\n",
    "            idx2 = bisect_left(nums,0)\n",
    "            tot = 1\n",
    "            for i in range(idx, n):\n",
    "                tot *= nums[i]\n",
    "            if idx2 % 2== 1:\n",
    "                for i in range(idx2-1):\n",
    "                    tot *= nums[i] \n",
    "            else:\n",
    "                for i in range(idx2):\n",
    "                    tot *= nums[i]\n",
    "            return tot \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxStrength(self, nums):\n",
    "        if len(nums) == 1: return nums[0]        \n",
    "        lstneg = [n for n in nums if n < 0]\n",
    "        if len(lstneg) & 1: \n",
    "            nums.remove(max(lstneg))\n",
    "        nums = [n for n in nums if n]\n",
    "        return reduce(lambda x, y : x * y, nums) if nums else 0        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        mx, mn = nums[0], nums[0]\n",
    "        for x in nums[1:]:\n",
    "            t1, t2 = mx, mn\n",
    "            mx = max(x, t1, x * t1, x * t2)\n",
    "            mn = min(x, t2, x * t1, x * t2)\n",
    "            #print(mx, mn)\n",
    "        return max(mx, mn)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        nums_1, nums_2 = [], []\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] > 0:\n",
    "                nums_1.append(nums[i])\n",
    "            elif nums[i] < 0:\n",
    "                nums_2.append(nums[i])\n",
    "                nums_2.sort()\n",
    "        if nums_1 == [] and len(nums_2) < 2:\n",
    "            if 0 in nums:\n",
    "                return 0\n",
    "            else:\n",
    "                return nums_2[0]\n",
    "        nums_3 = 1\n",
    "        for i in nums_1:\n",
    "            nums_3 = nums_3 * i\n",
    "        if nums_2 == []:\n",
    "                return nums_3\n",
    "        if len(nums_2) % 2 == 1:\n",
    "            for i in range(0, len(nums_2) - 1):\n",
    "                nums_3 = nums_3 * nums_2[i]\n",
    "        else:\n",
    "            for i in range(0, len(nums_2)):\n",
    "                nums_3 = nums_3 * nums_2[i]\n",
    "        return nums_3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxStrength(self, nums):\n",
    "        if len(nums) == 1: return nums[0]        \n",
    "        lstneg = [n for n in nums if n < 0]\n",
    "        if len(lstneg) & 1: \n",
    "            nums.remove(max(lstneg))\n",
    "        nums = [n for n in nums if n]\n",
    "        return reduce(lambda x, y : x * y, nums) if nums else 0        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        A=[]\n",
    "        B=[]\n",
    "        o=0\n",
    "        for i in nums:\n",
    "            if i>0:\n",
    "                A.append(i)\n",
    "            elif i==0:\n",
    "                o+=1\n",
    "            else:\n",
    "                B.append(i)\n",
    "        if len(B)==0:\n",
    "            if len(A)==0:\n",
    "                return 0\n",
    "            else:\n",
    "                s=1\n",
    "                for i in A:\n",
    "                    s*=i\n",
    "                return s\n",
    "        elif len(B)==1:\n",
    "            if len(A)==0:\n",
    "                if o==0:\n",
    "                    return B[0]\n",
    "                else:\n",
    "                    return 0\n",
    "            else:\n",
    "                s=1\n",
    "                for i in A:\n",
    "                    s*=i\n",
    "                return s\n",
    "        else:\n",
    "            s=1\n",
    "            m=9\n",
    "            for i in B:\n",
    "                m=min(m,abs(i))\n",
    "                s*=abs(i)\n",
    "            if len(B)%2==1:\n",
    "                s=s//m\n",
    "            for i in A:\n",
    "                s*=i\n",
    "            return s\n",
    "                \n",
    "                    \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "\n",
    "        nums = sorted(nums)\n",
    "\n",
    "        \n",
    "        neg = 0\n",
    "\n",
    "        pos_mult = 1\n",
    "        for x in nums:\n",
    "            if x<0:\n",
    "                neg += 1\n",
    "            if x>0:\n",
    "                pos_mult *= x \n",
    "        \n",
    "        if neg%2==1:\n",
    "            neg = neg-1\n",
    "        \n",
    "        cnt = 0 \n",
    "        for x in nums:\n",
    "            if x<0 and cnt<neg:\n",
    "                pos_mult *= x \n",
    "                cnt += 1\n",
    "        if nums[-1]<=0 and neg==0:\n",
    "            return nums[-1]\n",
    "        \n",
    "        return pos_mult\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        assert n>0\n",
    "        if n==1:\n",
    "            return nums[0]\n",
    "        c0 = nums.count(0)\n",
    "        if c0==n or (c0+1==n and sum(nums)<0):\n",
    "            return 0\n",
    "\n",
    "        p=1\n",
    "        maxneg=-inf\n",
    "        negcnt=0\n",
    "        for x in nums:\n",
    "            if x==0:\n",
    "                continue\n",
    "            p*=x\n",
    "            if x<0:\n",
    "                negcnt+=1\n",
    "                if x>maxneg:\n",
    "                    maxneg=x\n",
    "        if negcnt%2==1:\n",
    "            p//=maxneg\n",
    "        return p\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        # ans=-inf\n",
    "        # def dfs(i:int,prod:int,is_empty:bool)->int:\n",
    "        #     if i==len(nums):\n",
    "        #         if not is_empty:\n",
    "        #             nonlocal ans\n",
    "        #             ans=max(ans,prod)\n",
    "        #         return\n",
    "        #     dfs(i+1,prod*nums[i],False)\n",
    "        #     dfs(i+1,prod,is_empty)\n",
    "        # dfs(0,1,True)\n",
    "        # return ans\n",
    "        mx=mn=nums[0]\n",
    "        for x in nums[1:]:\n",
    "            tmp=mx\n",
    "            mx=max(mx,x,mx*x,mn*x)\n",
    "            mn=min(mn,x,mn*x,tmp*x)\n",
    "        return mx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: [int]) -> int:\n",
    "        nm = len(nums)\n",
    "        tot=-sys.maxsize\n",
    "\n",
    "        res = [1 for _ in range(1 << nm)]  # 2**n种可能的（n种子集的和）\n",
    "\n",
    "        for i in range(nm):\n",
    "            for j in range(1 << i):\n",
    "                res[(1 << i) + j] = nums[i]*res[j]\n",
    "                tot=max(tot,res[(1 << i) + j])\n",
    "\n",
    "        return tot\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        def dfs(idx, cnt, cur_product):\n",
    "            nonlocal res\n",
    "            if idx == len(nums):\n",
    "                if cnt > 0:\n",
    "                    res = max(res, cur_product)\n",
    "                return\n",
    "            dfs(idx + 1, cnt + 1, cur_product * nums[idx])\n",
    "            dfs(idx + 1, cnt, cur_product)\n",
    "\n",
    "        res = float('-inf')\n",
    "        dfs(0, 0, 1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        tot = 1 \n",
    "        arr = []\n",
    "        flag1, flag2 = 0, 0 \n",
    "        flag3 = 0\n",
    "        for x in nums:\n",
    "            if x > 0:\n",
    "                flag1 = 1 \n",
    "                tot *= x \n",
    "            elif x < 0:\n",
    "                arr.append(x) \n",
    "            else:\n",
    "                flag3 = 1\n",
    "        arr.sort() \n",
    "        m = len(arr) \n",
    "        if m % 2 == 0:\n",
    "            for x in arr:\n",
    "                flag2 = 1\n",
    "                tot *= x \n",
    "        else:\n",
    "            for x in arr[:-1]:\n",
    "                flag2 = 1\n",
    "                tot *=x \n",
    "        if flag1 == 0:\n",
    "            if flag2 == 1:\n",
    "                return tot \n",
    "            elif flag3:\n",
    "                return 0 \n",
    "            else:\n",
    "                return arr[-1]\n",
    "\n",
    "        return tot "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        ans = -inf\n",
    "\n",
    "        def dfs(i:int,prod:int,empty:bool)->int:\n",
    "            if i<0:\n",
    "                if not empty:\n",
    "                    nonlocal ans \n",
    "                    ans = max(ans,prod)\n",
    "                return\n",
    "                 \n",
    "            dfs(i-1, prod * nums[i],False) \n",
    "            dfs(i-1, prod,empty)\n",
    "\n",
    "        dfs(n-1,1,True)\n",
    "\n",
    "        return ans \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        ans=-inf\n",
    "        def dfs(i:int,prod:int,is_empty:bool)->int:\n",
    "            if i==len(nums):\n",
    "                if not is_empty:\n",
    "                    nonlocal ans\n",
    "                    ans=max(ans,prod)\n",
    "                return\n",
    "            dfs(i+1,prod*nums[i],False)\n",
    "            dfs(i+1,prod,is_empty)\n",
    "        dfs(0,1,True)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, a: List[int]) -> int:\n",
    "        ans=-inf\n",
    "        n=len(a)\n",
    "        def dfs(p,t):\n",
    "            if p>=n:\n",
    "                nonlocal ans\n",
    "                ans=max(ans,t)\n",
    "                return\n",
    "            dfs(p+1,t*a[p] if t!=-inf else a[p])\n",
    "            dfs(p+1,t)\n",
    "        dfs(0,-inf)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxStrength(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans=-float(\"inf\")\n",
    "        #nums=nums\n",
    "        def dfs(i,v,q):\n",
    "           # print(v)\n",
    "            nonlocal ans\n",
    "            if i==n:\n",
    "                if q!=0:\n",
    "                    ans=max(v,ans)\n",
    "                #print(v)\n",
    "                return\n",
    "           \n",
    "            dfs(i+1,v*nums[i],q+1)\n",
    "            dfs(i+1,v,q)\n",
    "            return \n",
    "\n",
    "        dfs(0,1,0)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
